---
title: "L2-045 堆宝塔"
created: 2025-11-28
tags:
  - 算法
---

# L2-045 堆宝塔

## 题目 [L2-045 堆宝塔](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1649748772841508872&page=1)

![[image-1173b7de.png]]

## 思路分析

![[image-3db06964.png]]

- 初始用 `A柱` 放第一块，准备两个栈 `a, b`。
- 对于当前圈 `C`：
  - 若 `C < a.top()`，放到 `A`。
  - 否则，如果 `B` 为空或 `C > b.top()`，放到 `B`。
  - 否则，视为 A 上的塔完成（`ans[cnt] = A 的一整个塔`），计数器 `cnt++`，并清空 `A`；
    - 然后把 `B` 中比 `C` 大的一个个放到 `A` 上；
    - 最后把 `C` 放到 `A`。
- 最后：
  - 把当前 `A` 作为一座塔收下；
  - 把剩余的 `B` 依次放入新的塔中（反向插入）。

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

vector<int> nums;

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	nums.resize(n);

	for(int i=0;i<n;i++){

		cin>>nums[i];

	}

	stack<int> a,b;

	vector<deque<int>> towers;

	for(int i=0;i<n;i++){

		int c=nums[i];

		if(a.empty() || a.top()>c)	a.push(c);

		else if(b.empty() || c>b.top())	b.push(c);

		else{

			deque<int> tmp;

			while(!a.empty()){

				tmp.push_front(a.top());

				a.pop();

			}

			towers.push_back(tmp);

			while(!b.empty() && b.top()>c){

				a.push(b.top());

				b.pop();

			}

			a.push(c);

		}

	}

	if(!a.empty()){

		deque<int> tmp;

		while(!a.empty()){

			tmp.push_front(a.top());

			a.pop();

		}

		towers.push_back(tmp);

	}

	if(!b.empty()){

		deque<int> tmp;

		while(!b.empty()){

			tmp.push_front(b.top());

			b.pop();

		}

		towers.push_back(tmp);

	}

	int tower_cnt=towers.size();

	int max_height=-inf;

	for(auto d:towers){

		int curs=d.size();

		max_height=max(max_height,curs);

	}

	cout << tower_cnt << " " << max_height << endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-044 大众情人|L2-044 大众情人]] 🏠 [[00-天梯赛]] ➡️ [[L2-046 天梯赛的赛场安排|L2-046 天梯赛的赛场安排]]